#include <string.h>
#include "Sort.h"


void MergeSortBad(ElemType arr[], int len) {
	if (len < 2) {
		// Boundary condition.
	}
	else {
		int len1 = len / 2;
		int len2 = len - len1;
		ElemType arr1[len1], arr2[len2];
		memcpy(arr1, arr, len1 * sizeof(ElemType));
		memcpy(arr2, &arr[len1], len2 * sizeof(ElemType));

		MergeSort(arr1, len1);
		MergeSort(arr2, len2);

		int idx1 = 0, idx2 = 0;
		while (idx1 < len1 && idx2 < len2) {
			if (arr1[idx1] < arr2[idx2]) {
				arr[idx1+idx2] = arr1[idx1];
				idx1 += 1;
			}
			else {
				arr[idx1+idx2] = arr2[idx2];
				idx2 += 1;
			}
		}
		if (idx1 == len1) {
			memcpy(&arr[idx1+idx2], &arr2[idx2], (len2 - idx2) * sizeof(ElemType));
		}
		else {
			memcpy(&arr[idx1+idx2], &arr1[idx1], (len1 - idx1) * sizeof(ElemType));
		}
	}
}


void MergeSort(ElemType arr[], int len) {
	if (len < 2) {
		// Boundary condition.
	}
	else {
		int len1 = len / 2;
		int len2 = len - len1;
		ElemType* arr1 = arr;
		ElemType* arr2 = &arr[len1];

		MergeSort(arr1, len1);
		MergeSort(arr2, len2);

		ElemType tmpArr[len];
		int idx1 = 0, idx2 = 0;
		while (idx1 < len1 && idx2 < len2) {
			if (arr1[idx1] < arr2[idx2]) {
				tmpArr[idx1+idx2] = arr1[idx1];
				idx1 += 1;
			}
			else {
				tmpArr[idx1+idx2] = arr2[idx2];
				idx2 += 1;
			}
		}
		if (idx1 == len1) {
			memcpy(&tmpArr[idx1+idx2], &arr2[idx2], (len2 - idx2) * sizeof(ElemType));
		}
		else {
			memcpy(&tmpArr[idx1+idx2], &arr1[idx1], (len1 - idx1) * sizeof(ElemType));
		}
		memcpy(arr, tmpArr, len * sizeof(ElemType));
	}
}
